<head>
    <meta charset="UTF-8">
<title>算法训练 magicsticks</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>&nbsp;</p>
<p>【问题描述】</p>
<p>对于古代居民来说，魔法是一种借助神力的技术。在一个有名的故事里魔杖，一&nbsp;</p>
<p>群男巫把他们的魔杖扔在地上，这些魔杖神奇地变成了活生生的蛇。然而，另一</p>
<p>&nbsp;个人将他的魔杖扔在地上时，它变成的蛇则吃掉了男巫们的蛇！</p>
<p>男巫们为了对付这个蛋疼的事情，需要解决以下问题：你有一根魔棒，它是一条&nbsp;</p>
<p>由若干条给定长度的线段组成的折线，折线的所有顶点都可以任意折叠。这条折&nbsp;</p>
<p>线通过折叠可以围成若干个多边形。你需要最大化这些多边形的面积之和，注意&nbsp;</p>
<p>，折线上的每一条线段都至多被用于一个多边形。线段只能在它们的端点上相交&nbsp;</p>
<p>。</p>
<p>左图的折线由五条线段和四个可折叠的轴组成，它可以被折叠成右图那样的多边&nbsp;</p>
<p>形。</p>
<p><img src="http://lx.lanqiao.cn/RequireFile.do?fid=27G6NJeD" width="826" height="99" alt="" /></p>
<p>【输入格式】</p>
<p>输入的第一行一个整数n，表示这条折线包含的线段数。</p>
<p>下一行共n个数，顺次给出每条线段的长度s1,s2,...,sn</p>
<p>【输出格式】</p>
<p>一个实数表示多边形的最大面积和</p>
<p>【样例输入】</p>
<p>样例1：</p>
<p>4</p>
<p>1 2 3 4</p>
<p>样例2：</p>
<p>8</p>
<p>3 4 5 33 3 4 3 5</p>
<p>【样例输出】</p>
<p>样例1：4.898979</p>
<p>样例2：19.311</p>
<p>【数据规模和约定】</p>
<p>3&lt;=n&lt;=500, 1&lt;=si&lt;=1000</p>
<p>&nbsp;</p>